package com.computer.fundamentals.datastructure;

import com.computer.util.Constant;

import java.util.HashMap;
import java.util.Map;

/**
 * LFU（least frequently used (LFU) page-replacement algorithm）,即最不经常使用页置换算法.
 * 定义：
 *      LFU根据数据的历史访问频率来淘汰数据，其核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。
 */
public class LFUCache {

    static class LFUDoubleLinkedNode {
        int val;
        int key;
        int freq;
        LFUDoubleLinkedNode prev;
        LFUDoubleLinkedNode next;

        public LFUDoubleLinkedNode() {}

        public LFUDoubleLinkedNode(int key, int val) {
            this.key = key;
            this.val = val;
            this.freq = 1;
        }
    }

    static class LFUDoubleLinkedList {

        public LFUDoubleLinkedNode head;
        public LFUDoubleLinkedNode tail;

        public LFUDoubleLinkedList() {
            this.head = new LFUDoubleLinkedNode();
            this.tail = new LFUDoubleLinkedNode();
            head.next = tail;
            tail.prev = head;
        }

        /**
         * 插入节点
         */
        private void addToHead(LFUDoubleLinkedNode node) {
            head.next.prev = node;
            node.next = head.next;
            node.prev = head;
            head.next = node;
        }

        /**
         * 删除节点
         */
        private void remove(LFUDoubleLinkedNode node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        /**
         * 删除尾部节点
         */
        private LFUDoubleLinkedNode removeLast() {
            LFUDoubleLinkedNode node = tail.prev;
            remove(node);
            return node;
        }

    }

    public int capacity; // 最大容量
    public int size; // 当前容量
    public Map<Integer, LFUDoubleLinkedList> freqMap; // 相同频次链表
    public Map<Integer, LFUDoubleLinkedNode> cache; // 节点存储
    public int minFreq; // 当前最小频次

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.minFreq = 0;
        freqMap = new HashMap<>();
        cache = new HashMap<>();
    }

    /**
     * 获取页面
     */
    public int get(int key) {
        LFUDoubleLinkedNode node = cache.get(key);
        if (node == null) {
            throw new RuntimeException(Constant.PAGE_IS_NOT_EXIST);
        }
        updateFreq(node);
        return node.val;
    }

    /**
     * 插入页面
     */
    public void put(int key, int val) {
        if (capacity == 0) {
            throw new RuntimeException(Constant.CACHE_CAPACITY_ZERO);
        }
        LFUDoubleLinkedNode node = cache.get(key);
        if (node == null) {
            if (size == capacity) {
                LFUDoubleLinkedList minLfuDoubleLinkedList = freqMap.get(minFreq);
                LFUDoubleLinkedNode lfuDoubleLinkedNode = minLfuDoubleLinkedList.removeLast();
                cache.remove(lfuDoubleLinkedNode.key);
                size--;
            }
            node = new LFUDoubleLinkedNode(key, val);
            cache.put(key, node);
            LFUDoubleLinkedList lfuDoubleLinkedList = freqMap.get(node.freq);
            if (lfuDoubleLinkedList == null) {
                lfuDoubleLinkedList = new LFUDoubleLinkedList();
                freqMap.put(node.freq, lfuDoubleLinkedList);
            }
            lfuDoubleLinkedList.addToHead(node);
            size++;
            minFreq = 1;
        }else {
            node.val = val;
            updateFreq(node);
        }
    }

    /**
     * 更新频次
     */
    public void updateFreq(LFUDoubleLinkedNode node) {
        // 删除老频次链表中的节点
        int freq = node.freq;
        LFUDoubleLinkedList lfuDoubleLinkedListOld = freqMap.get(freq);
        lfuDoubleLinkedListOld.remove(node);

        // 更新当前最小频次
        if (freq == minFreq && lfuDoubleLinkedListOld.head.next == lfuDoubleLinkedListOld.tail) {
            minFreq = freq+1;
        }

        // 插入到新频次链表
        node.freq = freq + 1;
        LFUDoubleLinkedList lfuDoubleLinkedListNew = freqMap.get(node.freq);
        if (lfuDoubleLinkedListNew == null) {
            lfuDoubleLinkedListNew = new LFUDoubleLinkedList();
            freqMap.put(node.freq, lfuDoubleLinkedListNew);
        }
        lfuDoubleLinkedListNew.addToHead(node);
    }

    /**
     * 测试,详细测试前往 https://leetcode-cn.com/problems/lfu-cache/submissions/
     */
    public static void main(String[] args) {

        LFUCache lfuCache = new LFUCache(2);
        System.out.println("------------LFU测试------------");
        lfuCache.put(3, 1);
        lfuCache.put(2, 1);
        lfuCache.put(2, 2);
        lfuCache.put(4, 4);
        System.out.println(lfuCache.get(2));

    }
}